package 最小的k个数;

import jdk.nashorn.internal.ir.CallNode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution
{
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k)
    {
        //方法一，升序排序，给出前k的数，nlogn
        //方法二，不必对整个数组排序，只需前k个,冒泡排序，外循环运行k次，只排前k个
        //方法三，利用快排的Partition函数，先找出k个的位置，它前面的数都比他小，但是排序不对，再排序O（n），适合数组可以更改的情况
        //方法四，大顶堆的方法，适合海量数据 nlogk

        //java中的优先队列是用堆实现的
        ArrayList<Integer> list = new ArrayList<>();
        if (input==null||input.length==0||k<=0||k>input.length)
            return list;

        PriorityQueue<Integer> pq=new PriorityQueue<Integer>(k, new Comparator<Integer>()
        {
            @Override
            public int compare(Integer o1, Integer o2)
            {
                return o2.compareTo(o1);//o2大于o1，返回1，=0，小于返回-1，设置为了大顶堆
            }
        });

        for (int i = 0; i < input.length; i++)
        {
            if (pq.size()!=k)
            {
                pq.offer(input[i]);
            }
            else if (pq.peek()>input[i])
            {
                pq.poll();
                pq.offer(input[i]);
            }

        }
        for (Integer integer:
             pq)
        {
            list.add(integer);
        }
        return list;
    }
    public ArrayList<Integer> GetLeastNumbers_Solution1(int [] input, int k)
    {
        ArrayList<Integer> list = new ArrayList<>();
        if (input==null||input.length==0||k<=0||k>input.length)
            return list;

        for (int i = 0; i < k; i++)
        {
            for (int j = 0; j < input.length-i-1;j++)
            {
                if (input[j]<input[j+1])
                {
                    int temp = input[j];
                    input[j] = input[j + 1];
                    input[j + 1] = temp;
                }
            }
            list.add(input[input.length-i-1]);
        }
        return list;
    }

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        System.out.println(solution.GetLeastNumbers_Solution1(new int[]{4,5,1,6,2,7,3,8},4));
    }
}
